package com.hanxiaozhang.tree;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈二叉树基础〉
 *
 * @author hanxinghua
 * @create 2021/9/16
 * @since 1.0.0
 */
public class BinaryTreeBase {


    /**
     * 举例：
     * ----------1
     * -------/    \
     * ------2      3
     * ----/  \   /  \
     * ---4    5 6    7
     *
     * @param args
     */
    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
//        // 递归先序
//        // 1 2 4 5 3 6 7
//        pre(head);
//        System.out.println("----------");
//        // 递归中序
//        // 4 2 5 1 6 3 7
//        mid(head);
//        System.out.println("----------");
//        // 递归后序
//        // 4 5 2 6 7 3 1
//        pos(head);
//        System.out.println("----------");
//        // 递归序解释，先中后序
//        recursion(head);
//        System.out.println("----------");
//        // 栈先序
//        preStack(head);
//        System.out.println("----------");
//        // 栈中序
//        midStack(head);
//        System.out.println("----------");
//        // 栈后序
//        posStack(head);
//        System.out.println("----------");
//        // 栈后序1
//        posStack1(head);
//        System.out.println("----------");
//        // 按层遍历
//        // 1 2 3 4 5 6 7
//        layerFor(head);
//        System.out.println("----------");
        // 先序方式序列化
        Queue queue = serializationByPre(head);
        // 先序方式反序列化
        deserializationByPre(queue);
        System.out.println("----------");
        // 按层序列化
        Queue queue1 = serializationByLayer(head);
        // 按层反序列化
        deserializationByLayer(queue1);
    }


    /**
     * 按层序列化
     *
     * @param head
     * @return
     */
    public static Queue<Integer> serializationByLayer(Node head) {

        Queue<Integer> queue = new LinkedList<>();
        if (head == null) {
            queue.add(null);
        } else {
            queue.add(head.value);
            Queue<Node> tmp = new LinkedList<>();
            tmp.add(head);
            while (!tmp.isEmpty()) {
                Node node = tmp.poll();
                if (node.left != null) {
                    tmp.add(node.left);
                    queue.add(node.value);
                } else {
                    queue.add(null);
                }
                if (node.right != null) {
                    tmp.add(node.right);
                    queue.add(node.value);
                } else {
                    queue.add(null);
                }
            }
        }
        return queue;
    }

    /**
     * 按层反序列化
     *
     * @param queue
     * @return
     */
    public static Node deserializationByLayer(Queue<Integer> queue) {
        if (queue == null || queue.size() == 0) {
            return null;
        }
        // 创建出头结点
        Node head = generateNode(queue.poll());
        // 临时队列
        Queue<Node> tmp = new LinkedList<>();
        if (head != null) {
            tmp.add(head);
        }
        Node node = null;
        // 临时队列不为空
        while (!tmp.isEmpty()) {
            // 弹出临时队列节点 node
            node = tmp.poll();
            // node的左右孩子节点从queue依次弹出
            node.left = generateNode(queue.poll());
            node.right = generateNode(queue.poll());
            if (node.left != null) {
                tmp.add(node.left);
            }
            if (node.right != null) {
                tmp.add(node.right);
            }
        }
        return head;
    }

    private static Node generateNode(Integer value) {
        if (value == null) {
            return null;
        }
        return new Node(value);
    }


    /**
     * 先序方式序列化
     *
     * @param head
     * @return
     */
    public static Queue<Integer> serializationByPre(Node head) {
        Queue<Integer> queue = new LinkedList<>();
        serializationByPre(head, queue);
        return queue;
    }

    private static void serializationByPre(Node head, Queue<Integer> queue) {
        if (head == null) {
            queue.add(null);
        } else {
            queue.add(head.value);
            serializationByPre(head.left, queue);
            serializationByPre(head.right, queue);
        }
    }


    /**
     * 先序反序列化
     *
     * @return
     */
    public static Node deserializationByPre(Queue<Integer> queue) {
        if (queue == null || queue.isEmpty()) {
            return null;
        }
        return buildTreeByPre(queue);
    }

    private static Node buildTreeByPre(Queue<Integer> queue) {
        Integer value = queue.poll();
        if (value == null) {
            return null;
        }
        Node head = new Node(value);
        head.left = buildTreeByPre(queue);
        head.right = buildTreeByPre(queue);
        return head;

    }


    /**
     * 按层遍历
     * <p>
     * 流程：
     * 1. 首先把头结点放入队列
     * 2. 循环判断队列是否为空
     * 3. 不为空，打印队列弹出节点，并且将弹出节点的左右孩子节点存入队列。
     * 4. 循环执行 2 3
     *
     * @param head
     */
    public static void layerFor(Node head) {
        if (head == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        System.out.println();
    }


    /**
     * 递归序
     * 先序：第一次到达的节点
     * 中序：第二次到达的节点
     * 后序：第三次到达的节点
     *
     * @param head
     */
    public static void recursion(Node head) {
        if (head == null) {
            return;
        }
        System.out.println("先 is " + head.value);
        recursion(head.left);
        System.out.println("中 is " + head.value);
        recursion(head.right);
        System.out.println("后 is " + head.value);
    }


    /**
     * 递归先序遍历
     * 任何子树的处理顺序都是，先头节点、再左子树、然后右子树
     */
    public static void pre(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + " ");
        pre(head.left);
        pre(head.right);
    }


    /**
     * 递归中序遍历
     * 任何子树的处理顺序都是，先左子树、再头节点、然后右子树
     *
     * @param head
     */
    public static void mid(Node head) {
        if (head == null) {
            return;
        }
        mid(head.left);
        System.out.print(head.value + " ");
        mid(head.right);
    }

    /**
     * 递归后序遍历
     * 任何子树的处理顺序都是，先左子树、再右子树、然后头节点
     *
     * @param head
     */
    public static void pos(Node head) {
        if (head == null) {
            return;
        }
        pos(head.left);
        pos(head.right);
        System.out.print(head.value + " ");

    }

    /**
     * 先序遍历非递归版
     * <p>
     * 规则：
     * 1. 弹出就打印
     * 2. 如果有右孩子，压入右
     * 3. 如有左孩子，压入左
     *
     * @param head
     */
    public static void preStack(Node head) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            // 压入头结点
            stack.add(head);
            // 栈不为空，一直循环
            while (!stack.isEmpty()) {
                // 弹出头结点
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }


    /**
     * 后序打印非递归版
     * <p>
     * 把preStack要打印的结果存入一个栈，
     * 然后弹出栈中元素
     *
     * @param head
     */
    public static void posStack(Node head) {
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }


    /**
     * 中序遍历非递归版本
     * <p>
     * 规则：
     * 1. 整条左边界依次入栈
     * 2. 1无法再继续，弹出结点并打印，来的结点的树上继续执行1
     *
     * @param head
     */
    public static void midStack(Node head) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }


    /**
     * 后序遍历非递归
     * 1:00:00
     *
     * @param head
     */
    public static void posStack1(Node head) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.push(head);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                // 左树，有没有处理
                if (c.left != null && head != c.left && head != c.right) {
                    stack.push(c.left);
                    // 右树，有没有处理
                } else if (c.right != null && head != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    head = c;
                }
            }
        }
        System.out.println();
    }

}
